import java.util.ArrayList;
import java.util.List;

/**
 * 1750. 删除字符串两端相同字符后的最短长度
 * https://leetcode-cn.com/problems/minimum-length-of-string-after-deleting-similar-ends/
 */
public class Solutions_1750 {
    public static void main(String[] args) {
        String s1 = "ca";  // output: 2
        String s2 = "cabaabac";  // output: 0
        String s3 = "aabccabba";  // output: 3
        String s4 = "aabbbbbba";  // output: 0
        String s5 = "bbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbccbcbcbccbbabbb";  // output: 1
        String s6 = "bcbcb";  // output: 1

        List<String> inputs = new ArrayList<>();
        inputs.add(s1);
        inputs.add(s2);
        inputs.add(s3);
        inputs.add(s4);
        inputs.add(s5);
        inputs.add(s6);

        for (String input : inputs) {
            int result = minimumLength(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：双指针模拟
     */
    public static int minimumLength(String s) {
        if (s == null) {
            return 0;
        }
        char[] arr = s.toCharArray();
        int len = arr.length;
        int left = 0, right = len - 1;

        // 前缀和后缀的字符相同时，左右指针向中心靠拢
        while (left < right && arr[left] == arr[right]) {
            char c = arr[left];
            // 尽可能多地消除相同前缀
            while (left <= right && arr[left] == c) {
                left ++;
            }
            // 尽可能多地消除相同后缀
            while (left <= right && arr[right] == c) {
                right --;
            }
        }
        // 若全部消除了，则结果为 0，否则为 [left, right] 区间的长度
        return right - left + 1;
    }
}
